动态调度——示例
AP SHANTHI博士
该模块的目标是对经过动态调度的指令序列进行时钟级模拟。我们将研究数据结构如何维护相关信息以及如何处理危险。
我们首先回顾一下动态调度。动态调度是一种技术，其中硬件重新安排指令执行以减少停顿，同时保持数据流和异常行为。动态调度的优点是：
• 它处理在编译时依赖项未知的情况
– （例如，因为它们可能涉及内存引用）
•它简化了编译器
•它允许为一个管道编译的代码在不同的管道上高效运行
•硬件推测，一种具有显着性能优势的技术，基于动态调度
在动态调度的流水线中，所有指令按顺序通过发布阶段；然而，它们可以在第二阶段停止或相互绕过，从而进入乱序执行。指令也将无序完成。
为了允许指令乱序执行，我们需要对解码阶段做一些改变。到目前为止，我们假设在解码阶段，MIPS 流水线解码指令并从寄存器文件中读取操作数。现在，通过动态调度，我们进行了更改以启用乱序执行。解码阶段或发布阶段仅对指令进行解码并检查结构性危险。之后，指令将等待直到没有数据危险，然后再读取操作数。这将使我们能够按顺序发出、乱序执行和乱序完成。
整个簿记是在硬件中完成的。硬件考虑一组称为指令窗口的指令，并尝试根据操作数的可用性重新安排这些指令的执行。硬件维护每条指令的状态并决定每条指令何时从一个阶段移动到另一个阶段。动态调度程序在硬件中引入了寄存器重命名并消除了 WAW 和 WAR 危害。
在 Tomasulo 的方法中，寄存器重命名由保留站 (RS) 提供。与每个功能单元相关联，我们有几个保留站。当发出指令时，为其分配一个保留站。保留站存储有关指令的信息并缓存操作数值（如果可用）。因此，一旦操作数可用（不一定涉及寄存器文件），保留站就获取并缓冲该操作数。这有助于避免 WAR 危险。如果操作数不可用，它会存储有关提供操作数的指令的信息。重命名是通过寄存器和保留站之间的映射完成的。当一个功能单元完成其操作时，结果在结果总线上广播，称为公共数据总线 (CDB)。该值被写入适当的寄存器以及等待该数据的保留站。当两条指令要修改同一个寄存器时，只有最后一个输出更新寄存器文件，从而处理 WAW 危险。因此，寄存器说明符与保留站一起重命名，保留站可能多于寄存器。对于加载和存储操作，我们使用加载和存储缓冲区，其中包含数据和地址，并像保留站一样工作。
下面列出了动态调度程序中的三个步骤
• 问题
• 从 FIFO 队列中获取下一条指令
• 如果 RS 可用，则向 RS 发出具有操作数值的指令（如果可用）
• 如果 RS 不可用，它将成为结构性风险并且指令停止
• 如果没有发出较早的指令，则不能发出后续指令
• 如果操作数值不可用，指令将在 RS 中等待，在 CDB 中查找操作数
• 执行
• 当操作数在 CDB 上可用时，将其存储在任何等待它的保留站中
• 当所有操作数准备就绪时，指令由各自的功能单元执行
• 通过有效地址按程序顺序维护加载和存储
• 在按照程序顺序进行的所有分支都完成之前，不允许指令启动执行
• 写入结果
• 将 CDB 上的结果写入保留站并存储缓冲区
• 存储必须等到收到地址和值
动态调度器维护三种数据结构——保留站、保存将修改寄存器的指令的寄存器结果数据结构和指令状态数据结构。第三个更多是为了理解的目的。预留站组件如下图所示：
名称 - 识别预留站
Op——在单元中执行的操作（例如，+或-）
Vj、Vk - 源操作数的值
– 存储缓冲区有 V 字段，要存储的结果
Qj、Qk——产生源寄存器的保留站（要写入的值）
– 存储缓冲区只有用于 RS 产生结果的 Qi
Busy——表示预约站或FU忙
寄存器结果状态——指示哪个功能单元将写入每个寄存器（如果存在）。当没有将写入该寄存器的未决指令时，它是空白的。指令状态给出指令窗口中每条指令的状态。
图 17.1 显示了 Tomasulo 的动态调度程序的组织结构。指令从指令队列中取出并发出。在发布阶段，指令被解码并分配一个 RS 条目。如果可用，RS 站也会缓冲操作数。否则，RS 条目在 Q 字段中标记未决 RS 值。结果通过 CDB 传递到适当的寄存器，如寄存器结果数据结构以及未决 RS 所指示。
了解了 Tomasulo 动态调度程序的基础知识后，我们现在将讨论动态调度如何针对指令序列发生。我们只考虑一个没有分支的基本块。
图 17.2 显示了所考虑的指令序列以及所维护的三种数据结构。我们将假设三个Add保留站和两个Mul保留站。还有三个加载缓冲区。假设 Add 的延迟为 2，Mul 的延迟为 10，Div 的延迟为 40。
在第一个时钟周期内，发出 Load1。分配了一个加载缓冲区条目，它的状态现在是忙碌的，有效地址计算所需的 R2 的内容和值 34 存储在缓冲区中。寄存器结果状态显示寄存器 F6 将被 Load buffer1 标识的指令写入。
在第二个时钟周期内，Load1 从发出阶段移动到执行阶段。计算有效地址（34+R2）并存储在 Load buffer1 中。同时，发出指令2，即Load2。它被分配了 Load buffer entry2，有效地址（45，R3）的详细信息存储在那里。加载缓冲区 2 现在很忙。寄存器结果状态显示寄存器 F2 将被 Load buffer2 标识的指令写入。
在第三个时钟周期内，Load1 进行内存访问并完成执行。对于Load2，计算有效地址（45+R3）并存储在Load buffer2中。同时，发出指令3，即Mul。它被分配了 Mult1 条目，寄存器 F4 的内容被取出并存储在 V k 的位置。另一个操作数 F2 现在无法获取，必须等待 Load2 完成。这在 Q j字段中表示为 Load2。Mult1 保留站被标记为忙碌。寄存器结果状态显示寄存器 F0 将被 Mult1 标识的指令写入。这种情况如图 17.3 所示。
在第四个时钟周期内，Load1 将结果写入 CDB，相应的 Load1 条目被释放。CDB 上的这些数据写入 F6。Load2 进行内存访问并完成执行。同时，发出指令4，即Sub。它被分配了 Add1 条目，寄存器 F6 的内容被取出并存储在 V j 中。另一个操作数 F2 现在无法获取，必须等待 Load2 完成。这在 Q k字段中表示为 Load2。Add1 保留站被标记为忙。寄存器结果状态显示寄存器 F8 将被 Add1 标识的指令写入。请注意，Mul 仍在等待操作数并已停止。
在第五个时钟周期内，Load2 将结果写入 CDB，相应的 Load2 条目被释放。CDB 上的这些数据写入 F2。该数据被一直等待的Mult1预留站和Add1预留站占用。这两条指令 Sub 和 Mul 现在可以执行了。同时，发出指令5，即Div。它被分配了 Mult2 条目，寄存器 F6 的内容被取出并存储在 V k 中。另一个操作数 F0 现在无法获取，必须等待 Mul 完成。这在 Q j字段中表示为 Mult1。Mult2 保留站被标记为忙碌。寄存器结果状态显示寄存器F10 是由Mult2（Div 指令）标识的指令写入的。
在第6个时钟周期，Mul指令和Sub指令都经历了一个执行周期。同时，发出指令6，即Add。它被分配了 Add2 条目，寄存器 F2 的内容被取出并存储在 V k 中。另一个操作数 F8 现在无法获取，必须等待 Sub 完成。这在 Q j字段中表示为 Add1。Add2 保留站被标记为忙。寄存器结果状态显示寄存器 F6 将被 Add2（添加指令）标识的指令写入。图 17.4 描述了这种情况。
请注意，对于带有 Div 和 Sub 指令的 Add 指令，F6 存在名称依赖性，这可能会导致 WAR 危险。但是，由于Sub和Div指令的操作数F6已经在各自的保留站中被读取和缓存，因此通过寄存器重命名解决了名称依赖性，从而避免了可能的WAR危害。
Sub 指令在第七个时钟周期完成执行，因为它的延迟为 2。在这个时钟周期内没有其他任何事情发生。它在第 8 个时钟周期写入 CDB。Sub的结果写入寄存器F8，同时写入加减的保留站Add2。Add1 条目现在已释放。
时钟周期 9 – Add 和 Mul 仍在执行。在第 10 个时钟周期内，Add 完成执行，并在第 11 个时钟周期写入 CDB。该数据进入寄存器 F6，并释放 Add2 保留站条目。请注意，即使 Div 指令对寄存器 F6 存在名称依赖性，但这不会导致问题。Div指令的保留站已经通过Load1指令拿到了F6的原始数据。
在第 15 个时钟周期内，Mul 完成执行（延迟 10 – 时钟周期 6 到 15）并在第 16 个时钟周期写入结果。结果到寄存器 F0 和等待它的保留站 Mult2（Div 指令）。Mult1 条目被释放。Div 在第 17 个时钟周期开始执行并在第 56 个时钟周期完成执行（延迟为 40）。它将结果写入 57 并释放 Mult2 条目。完整的时间表如图 17.5 所示。观察指令是按顺序发出，乱序执行，乱序完成执行。
Tomasulo 的动态调度方式的优点如下：
(1) 危害检测逻辑的分布：
– Tomasulo 的方法使用分布式保留站和 CDB
– 如果多条指令在等待一个结果，并且每条指令都有其他操作数，则可以通过在 CDB 上广播的方式同时释放指令
– 如果使用集中式寄存器文件，则当寄存器总线可用时，单元必须从寄存器中读取其结果。
(2) 消除WAW和WAR危害的失速
– 保留站中操作数的缓冲，一旦它们变得可用，就在寄存器和保留站之间进行映射。此重命名过程可避免 WAR 危险。即使后续指令修改寄存器文件，也没有问题，因为操作数已经被读取和缓冲。
– 当两条或更多条指令写入同一个寄存器时，导致WAW危险，寄存器结果状态中只保留最新的寄存器信息。这种重命名避免了 WAW 危险。
然而，这种方法并非没有缺点。以下是缺点：
· 复杂性
o 记账完成后硬件变得复杂，CDB 和关联比较
· 很多关联商店（CDB）高速运行
· 性能受限于公共数据总线
o 每个 CDB 必须转到多个功能单元。这导致高电容和高布线密度
o 只有一个 CDB，每个周期可以完成的功能单元数量限制为一个！
§ 多个 CDB 将导致并行关联存储的更多 FU 逻辑
· 非精确中断！
o 乱序执行会导致不精确的中断。我们将在稍后讨论投机时讨论这个问题。
我们还没有讨论与内存位置相关的问题。他们也必须得到妥善处理。只要它们访问不同的地址，加载和存储就可以安全地无序完成。如果加载和存储访问相同的地址，则
· 加载在程序顺序存储之前，交换它们会导致 WAR 危害，或
· 存储在程序顺序加载之前，交换它们会导致 RAW 危害。
同样，将两个商店交换到同一地址会导致 WAW 危险。因此，为了确定是否可以在给定时间执行加载，处理器可以检查在程序顺序中加载之前的任何未完成存储是否与加载共享相同的数据存储器地址。类似地，存储必须等到没有未执行的加载或程序顺序较早的存储并共享相同的数据存储器地址。
总而言之，我们讨论了动态调度的一个例子，其中硬件在运行时动态重组代码。对于给定的指令序列，我们查看了时钟级模拟。已经详细说明了簿记完成和使用的各个步骤。在这个例子中我们没有处理分支。
网页链接/支持材料
计算机组织与设计——硬件/软件接口，David A. Patterson 和 John L. Hennessy，第 4 版，Morgan Kaufmann，Elsevier，2009 年。
Computer Architecture – A Quantitative Approach，John L. Hennessy 和 David A. Patterson，第 5 版，Morgan Kaufmann，Elsevier，2011。